/**
 * @Author ZhangCuirong
 * @Date 2025/9/3 16:06
 * @description:
 */
public class Solution45 {
    int []memo;
    public int jump(int[] nums) {
        memo = new int[nums.length];
        return dp(nums, 0);
    }

    int dp(int[] nums, int p) {
        if (p >= nums.length - 1) {
            return 0;
        }
        if (memo[p] != 0) {
            return memo[p];
        }
        int min = nums.length - 1;
        int steps = nums[p];
        for (int i = p + 1; i <= p + steps; i++) {
            min = Math.min(min, dp(nums, i) + 1);
        }
        memo[p] = min;
        return min;
    }
    public int jump2(int[] nums) {
       if(nums.length<=1){
           return 0;
       }
       int end = 0,jumps =0;
       int farthest = 0;
       for(int i=0;i<nums.length-1;i++){
           farthest = Math.max(farthest, i+nums[i]);
           if(i==end){
               jumps++;
               end = farthest;
               if(farthest>=nums.length-1){
                   return jumps;
               }
           }
       }
       return -1;
    }

    public static void main(String[] args) {
        Solution45 solution = new Solution45();
        System.out.println(solution.jump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(solution.jump(new int[]{2, 3, 0, 1, 4}));
    }
}
